package basic_datastructure.heap;

import java.util.Arrays;

public class BinaryHeap {
    /**
     * 二叉堆索引的计算关系
     *
     * 假设父节点的下标是 parent，那么它的左孩子下标就是2 * parent + 1, 右孩子下标就是2 * parent + 2
     *
     * 假设孩子节点（不论左右）的下标是 children， 那么孩子节点的父节点下标是 children - 1 / 2;
     */

    /**
     * 二叉堆的"上浮"调整，以最小堆为例。
     * <p>
     * 上浮调整，就是在二叉堆中插入一个元素。
     * <p>
     * 插入元素的位置永远是数组的最后一个位置(arr.length - 1)
     *
     * O(logN)
     */
    public static void upAdjust(int[] arr) {
        //插入元素的下标
        int childIndex = arr.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        while (childIndex > 0 && arr[childIndex] < arr[parentIndex]) {
            //插入的元素 < 其父节点值，交换
            swap(arr, childIndex, parentIndex);
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
    }

    /**
     * 二叉堆的"下沉"操作
     *
     * 构建最小堆，将parentIndex（父节点）位置的元素与孩子节点进行比较
     *
     * 如果父节点大于孩子节点，就将父节点与更小的孩子节点进行交换。
     *
     * O(logN)
     *
     * @param arr         待调整的堆
     * @param parentIndex 以该位置进行下沉操作
     * @param heapSize    "堆的有效大小"
     */
    public static void downAdjust(int[] arr, int parentIndex, int heapSize) {
        //记录一下左孩子的下标
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < heapSize) {
            //如果有右孩子，并且右孩子的值更小，则定位到右孩子
            if (childIndex + 1 < heapSize && arr[childIndex + 1] < arr[childIndex]) {
                childIndex++;
            }
            //如果父节点 <= 孩子节点 满足最小堆的性质，停止
            if (arr[parentIndex] <= arr[childIndex]) {
                break;
            }
            //交换父节点和孩子节点
            swap(arr, parentIndex, childIndex);
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
    }
    /*
        构建最大堆
     */
    public static void downAdjustMax(int[] arr, int parentIndex, int heapSize) {
        //记录一下左孩子的下标
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < heapSize) {
            //如果有右孩子，并且右孩子的值更大，则定位到右孩子
            if (childIndex + 1 < heapSize && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
            //如果父节点 > 孩子节点 满足最大堆的性质，停止
            if (arr[parentIndex] > arr[childIndex]) {
                break;
            }
            //交换父节点和孩子节点
            swap(arr, parentIndex, childIndex);
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
    }

    /**
     * 构建二叉堆，本质就是让所有的非叶子节点依次"下沉"
     *
     * O(N)
     * @param arr   将次数组构建成最小堆
     */
    public static void buildHeap(int[] arr){
        for (int i = arr.length / 2 - 1; i >= 0; i--){
            downAdjust(arr, i, arr.length);
        }
    }
    /**
     * 构建二叉堆，本质就是让所有的非叶子节点依次"下沉"
     * @param arr   将次数组构建成最大堆
     */
    public static void buildMaxHeap(int[] arr){
        for (int i = arr.length / 2 - 1; i >= 0; i--){
            downAdjustMax(arr, i, arr.length);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        upAdjust(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr2 = new int[]{10,9,8,7,6,5,4,3,2,1};
        downAdjust(arr2, 0, arr2.length);
        System.out.println(Arrays.toString(arr2));

        int[] arr3 = new int[]{7,1,3,10,5,2,8,9,6};
        buildHeap(arr3);
        System.out.println(Arrays.toString(arr3));

        int[] arr4 = new int[]{7,1,3,10,5,2,8,9,6};
        buildMaxHeap(arr4);
        System.out.println(Arrays.toString(arr4));
    }
}
